这道题明显是线段树的板题,至于考试时因为懒标记的小问题只有20分,我也很无奈。
进入正题,既然要修改查询区间内连续的一段元素,似曾相识的感觉。
我们等价的把空房子看为1,住人的房子看为0。
我们维护三个值: 表示这个区间最长的一段连续串 , 表示这个区间从左端点开始的最长连续串 , 表示这个区间从右端点开始的最长连续串。
然后,用f记录区间状态(懒标记),表示全为1,表示全为0,什么都没发生。
然后,就照着线段树的模板写。稍微麻烦一点的是区间修改后的维护与查询操作,下面来讲解一下。
1.区间修改后的维护(函数)
在得到两个子区间后,我们需要根据他们得出大区间的信息。(废话)
1.,
显然,大区间的就等于左区间的,特殊情况下,当左区间全为1时,大区间的等于左区间的长度加上右区间的。同理。
2.
显然,大区间的可能是两个小区间的的较大值,同时,也可能是由左区间的和右区间的拼接而成的连续‘1’串。
2.区间查询(函数)
应该比较好理解,哪个区间足够就查询哪个区间吗,注意输出最小的值,从左到右依次查询。
#include <cstdio>
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f
const int MAXN = 50000;
int n,m;
struct node{
int l , r , f;
int num , lnum , rnum;
}Tree[ 4 * MAXN + 5 ];
int Max( int x , int y ) {
return x > y ? x : y;
}
int Min( int x , int y ) {
return x < y ? x : y;
}
void Build( int x , int l , int r ) {
Tree[ x ].l = l , Tree[ x ].r = r , Tree[ x ].f = 2;
Tree[ x ].lnum = Tree[ x ].rnum = Tree[ x ].num = Tree[ x ].r - Tree[ x ].l + 1;
if( l == r ) return;
int Mid = ( l + r ) / 2;
Build( ls , l , Mid );
Build( rs , Mid + 1 , r );
}
void pushup( int x ) {
Tree[ x ].lnum = Tree[ ls ].lnum;
if( Tree[ ls ].num == Tree[ ls ].r - Tree[ ls ].l + 1 ) Tree[ x ].lnum = Tree[ ls ].num + Tree[ rs ].lnum;
Tree[ x ].rnum = Tree[ rs ].rnum;
if( Tree[ rs ].num == Tree[ rs ].r - Tree[ rs ].l + 1 ) Tree[ x ].rnum = Tree[ rs ].num + Tree[ ls ].rnum;
Tree[ x ].num = Max( Max( Tree[ ls ].num , Tree[ rs ].num ) , Tree[ ls ].rnum + Tree[ rs ].lnum );
}
void pushdown( int x ) {
if( Tree[ x ].l == Tree[ x ].r )
return;
if( Tree[ x ].f == 0 ) {
Tree[ ls ].num = 0 , Tree[ ls ].f = 0;
Tree[ rs ].num = 0 , Tree[ rs ].f = 0;
Tree[ ls ].lnum = Tree[ ls ].rnum = 0;
Tree[ rs ].lnum = Tree[ rs ].rnum = 0;
Tree[ x ].f = 2;
}
if( Tree[ x ].f == 1 ) {
Tree[ ls ].num = Tree[ ls ].r - Tree[ ls ].l + 1 , Tree[ ls ].f = 1;
Tree[ rs ].num = Tree[ rs ].r - Tree[ rs ].l + 1 , Tree[ rs ].f = 1;
Tree[ ls ].lnum = Tree[ ls ].rnum = Tree[ ls ].num;
Tree[ rs ].lnum = Tree[ rs ].rnum = Tree[ rs ].num;
Tree[ x ].f = 2;
}
}
void Insert( int x , int l , int r , int k ) {
if( l > Tree[ x ].r || Tree[ x ].l > r )
return;
if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
Tree[ x ].f = k;
Tree[ x ].num = k == 1 ? Tree[ x ].r - Tree[ x ].l + 1 : 0;
Tree[ x ].lnum = Tree[ x ].rnum = Tree[ x ].num;
return;
}
pushdown( x );
Insert( ls , l , r , k );
Insert( rs , l , r , k );
pushup( x );
}
int Find( int x , int k ) {
if( Tree[ x ].l == Tree[ x ].r ) return Tree[ x ].l;
pushdown( x );
if( Tree[ ls ].num >= k ) return Find( ls , k );
if( Tree[ ls ].rnum + Tree[ rs ].lnum >= k ) return Tree[ ls ].r - Tree[ ls ].rnum + 1;
if( Tree[ rs ].num >= k ) return Find( rs , k );
}
int main( ) {
//freopen("hotel.in","r",stdin);
//freopen("hotel.out","w",stdout);
scanf("%d %d",&n,&m);
Build( 1 , 1 , n );
int op,x,d;
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d",&op);
if( op == 1 ) {
scanf("%d",&d);
if( Tree[ 1 ].num < d ) {
printf("0\n");
continue;
}
int r = Find( 1 , d );
Insert( 1 , r , r + d - 1 , 0 );
printf("%d\n",r);
}
else if( op == 2 ) {
scanf("%d %d",&x,&d);
Insert( 1 , x , x + d - 1 , 1 );
}
}
return 0;
}